//
// Created by user on 2022/2/24.
//
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
    stack<char> st;
    for (char c:s){
        if(c=='(' || c=='{'||c=='['){
            st.push(c);
        }else{
            if(st.empty())return false;
            char topChar = st.top();
            st.pop();
            if(c==')' && topChar!='(')return false;
            if(c==']' && topChar!='[')return false;
            if(c=='}' && topChar!='{')return false;
        }
    }
    return st.empty();
}

bool isValid1(string s) {
    if (s.size() % 2 == 1) return false;

    unordered_map<char, char> map = {
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
    };

    stack<int> st;
    for (char c : s) {
        if (map.count(c)) {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char topChar = st.top();
            if (c != map[topChar]) return false;
            st.pop();
        }
    }
    return st.empty();
}